package 单调栈;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

public class DanDiaStack {

    public static void main(String[] args) {
        int[] nums = new int[]{2, 5, 4, 3};
        System.out.println(Arrays.deepToString(getNearLessNoRepeat(nums)));
        System.out.println(Arrays.deepToString(getNearLessRepeat(nums)));
    }

    public static int[][] getNearLessNoRepeat(int[] nums) {
        //定义结果
        int[][] res = new int[nums.length][2];
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
                //栈顶的index
                Integer topIndex = stack.pop();
                //如果是栈底没元素就-1，有就拿出来，但是不弹
                int leftIndex = stack.isEmpty() ? -1 : stack.peek();
                res[topIndex][0] = leftIndex;
                res[topIndex][1] = i;
            }
            //存index
            stack.push(i);
        }
        //处理后面剩下的栈中元素
        while (!stack.isEmpty()) {
            //右边就是-1
            Integer topIndex = stack.pop();
            //左边是看是不是最后一个
            int leftIndex = stack.isEmpty() ? -1 : stack.peek();
            res[topIndex][0] = leftIndex;
            res[topIndex][1] = -1;
        }
        return res;
    }

    //处理有重复值的
    public static int[][] getNearLessRepeat(int[] nums) {
        //定义结果
        int[][] res = new int[nums.length][2];
        Stack<List<Integer>> stack = new Stack<List<Integer>>();
        for (int i = 0; i < nums.length; i++) {
            //拿最上面栈顶链表的最新值比较，小于就结算
            while (!stack.isEmpty() && nums[stack.peek().get(0)] > nums[i]) {
                List<Integer> pops = stack.pop();
                //这里要拿最后一个
                int leftIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
                for (Integer index : pops) {
                    res[index][0] = leftIndex;
                    res[index][1] = i;
                }
            }
            //这里处理一样的值，放链表后面就行
            if (!stack.isEmpty() && nums[stack.peek().get(0)] == nums[i]) {
                List<Integer> peek = stack.peek();
                peek.add(i);
                stack.push(peek);
            } else {
                List<Integer> objects = new ArrayList<>();
                objects.add(i);
                stack.push(objects);
            }
        }
        //处理剩下的栈元素
        while (!stack.isEmpty()) {
            List<Integer> pops = stack.pop();
            for (Integer index : pops) {
                int leftIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.size() - 1);
                res[index][0] = leftIndex;
                res[index][1] = -1;
            }
        }
        return res;
    }

}
